package zuo.from0516.other.day07;

import zuo.from0516.other.day06.TreeNode;

import java.util.ArrayList;
import java.util.List;


/**
 * * Q98：验证二叉搜索树：
 *  * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *  * 有效 二叉搜索树定义如下：
 *  * 节点的左子树只包含 小于 当前节点的数。
 *  * 节点的右子树只包含 大于 当前节点的数。
 *  * 所有左子树和右子树自身必须也是二叉搜索树。
 *  * 思路：
 *  *  1）二叉树的中序遍历是严格递增的
 *  *  2）递归：根节点为value，如果左树的最大值小于value且右树的最小值大于value且整体是二叉搜索树
 */
public class Code05_IsBinarySearchTree {
    public static class Info{
        public int max;
        public int min;
        public boolean isBST;
        Info(int max,int min,boolean isBST){
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }
    public boolean isValidBinarySearchTree(TreeNode root){
        if (root == null){
            return true;
        }
        return getInfo(root).isBST;

    }

    public Info getInfo(TreeNode root){
        if (root == null){
            return null;
        }
        int max = root.value;
        int min = root.value;
        Info leftInfo = getInfo(root.left);
        Info rightInfo = getInfo(root.right);
        if (leftInfo != null){
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null){
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean leftLessX = leftInfo == null ? true : leftInfo.max < root.value;
        boolean rightMoreX = rightInfo == null ? true : rightInfo.min> root.value;
        boolean isBST = leftLessX && rightMoreX && (leftInfo == null ? true : leftInfo.isBST) && (rightInfo == null ? true : rightInfo.isBST);
        return new Info(max, min, isBST);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,null,null);
        root.left = new TreeNode(1,null,null);
        root.right = new TreeNode(4,null,null);
        root.right.left = new TreeNode(3,null,null);
        root.right.right = new TreeNode(6,null,null);

        boolean ans = isValidBST(root);
        System.out.println(ans);
    }

    public static boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        List<Integer> ans = new ArrayList<>();
        getList(root,ans);
        int pre = ans.get(0);
        for(int i=1;i<ans.size();i++){
            if(pre >= ans.get(i)){
                return false;
            }
            pre = ans.get(i);
        }
        return true;
    }
    public static void getList(TreeNode root,List<Integer> ans){
        if(root == null){
            return;
        }
        getList(root.left, ans);
        ans.add(root.value);
        getList(root.right, ans);
    }
}

